fn main() {
    println!("Hello, world!");
}
struct Solution;
impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        fn get_max(nums: &[i32]) -> i32 {
            let n = nums.len();
            let mut maxs = Vec::with_capacity(n + 1);
            maxs.push(0);
            maxs.push(nums[0]);
            for i in 1..n {
                maxs.push(maxs[i].max(maxs[i - 1] + nums[i]));
            }
            return maxs[n].max(maxs[n - 1]);
        }
        let n = nums.len();
        if n == 1 {
            return nums[0];
        }
        return get_max(&nums[0..n - 1]).max(get_max(&nums[1..n]));
    }
}
